Finite impulse response (FIR) filters are digital filters comprising a number of tap coefficients or weights. Samples of an input signal X(t) are shifted into the FIR filter one sample per cycle. At each cycle t, the FIR filter computes the sum y(t): ##EQU1## where, X(t-i) is a t-i.sup.th sample of X, P(i) is an i.sup.th tap coefficient of the FIR filter for 0.ltoreq.i.ltoreq.(n-1) and n is the number of tap coefficients of the FIR filter.
FIR filters are very useful in a number of applications, such as interpolation. FIG. 1 shows a polyphase interpolator 100 disclosed in J. Candy & G. Temes, "Oversampling Delta-Sigma Data Converters: Theory, Design and Simulation" PROC. OF THE I.E.E.E., vol. 69, no. 3, March, 1988 pp. 417-448. The interpolator 100 actually comprises L FIR filter banks 110-1, 110-2, . . . , 110-L which receive an inputted signal X(.left brkt-bot.t/L.right brkt-bot.) that has been oversampled by a factor of L. (Herein, ".left brkt-bot.C.right brkt-bot." means the nearest integer .ltoreq.C.)
The shifting in of samples X(.left brkt-bot.t/L.right brkt-bot.) for L times oversampled sample/hold data is illustrated in FIGS. 2(a)-(e). Assume that L=5 and n=3. Define a value v=t mod L. At a time t=0, v=0 and the samples are as shown in FIG. 2(a). As shown, the values in each filter bank 110-1 to 110-5 are the same. The filter banks 110-1 to 110-5 are thus said to be in phase. At time t=1, (v=1) a sample X(2) is shifted into the filter bank 110-1 as shown in FIG. 2(b). Thus, the filter bank 110-1 is out of phase with the filter banks 110-2 to 110-5. Likewise, FIGS. 2(c) shows the shifting of X(2) into the filter bank 110-2 at time t=2 for v=2. FIG. 2 (d) shows the shifting of X(2) into the filter bank 110-3 at time t=3 for v=3. FIG. 2(e) shows the shifting of X(2) into the filter bank 110-4 at time t=4 for v=4. Finally, FIG. 2(f) shows the shifting of X(2) into the filter bank 110-5 at time t=5 for v=0. In FIG. 2(f), the filter banks 110-1 to 110-5 are once again in phase.
The output of each FIR filter bank 110-1, 110-2, . . . , 110-L is fed to a corresponding upsampling circuit 120-1, 120-2, . . . , 120-L which upsamples the outputted signal L times. See D. ELLIOT, HANDBOOK OF DIGITAL SIGNAL PROCESSING ENGINEERING APPLICATIONS, p. 239 (1987). The upsampled, filtered signals y.sub.1 (t), y.sub.2 (t), . . . , y.sub.L (t) are then added together wherein each outputted upsampled, filtered signal, e.g., y.sub.L (t), is delayed by one cycle z.sup.-1 with respect to a preceding upsampled filtered signal, e.g., y.sub.L-1 (t), to produce an interpolation g(t) of the inputted samples at the time t, where: ##EQU2##
The problem with the interpolator 100 is that it requires many FIR filters which can occupy precious area on an IC chip. FIG. 3 shows another conventional polyphase interpolator 200 for use in audio applications. In the interpolator 200, it is assumed that: ##EQU3## for s.noteq.1, where s=t modulus L if (t modulus L).noteq.0 and s=L if t modulus L=0. Such an assumption is possible if the input signal X contains sample data. Thus, equation (2) can be simplified to: ##EQU4##
In FIG. 3, the interpolator 200 is provided with a RAM 210 for storing n input samples, e.g, X(0), X(1), . . . , X(n-1). Each sample is presumed to be a b bit number. Thus, the RAM 210 is an n.times.b bit RAM. An (L.times.n).times.d bit ROM 220 is also provided for storing each possible d bit tap coefficient P.sub.s (i) (where 1.ltoreq.s.ltoreq.L and 0.ltoreq.i.ltoreq.(n-1)). To compute g(t) at a particular time t, a controller (not shown) successively outputs n appropriate samples ##EQU5## and n corresponding tap coefficients P.sub.s (i) to the multiplier 230. The multiplier 230 multiplies each of the n samples with its corresponding tap coefficient and outputs each product thus formed to an accumulator 240. The accumulator 240 accumulates n such products to produce each g(t). The interpolator 200 thus utilizes n multiplications and n accumulations to produce each g(t).
If the input signal X contains sample/hold data, then equation (2) can be simplified as follows: ##EQU6## The conventional interpolator 200 can be modified to perform such a sample/hold interpolation. In particular, an (n+1).times.b bit RAM 210 is provided for storing n+1 input samples X(.left brkt-bot.t/L.right brkt-bot.), X(.left brkt-bot.t/L.right brkt-bot.-1), . . . , X(.left brkt-bot.t/L.right brkt-bot.-n). Likewise, an (L.times.(n+1)).times.d bit ROM 220 is provided for storing L.times.(n+1) different sums of tap coefficients, i.e., L, (n-1).times.L, and L sums of ##EQU7## respectively, for the three addends of equation (5). To compute each g(t) for each time t, a controller (not shown) sequentially outputs n+1 samples from the RAM 210 and n+1 corresponding sums of tap coefficients from the ROM 220 to the multiplier 230. The multiplier 230 outputs n+1 products which are accumulated in the accumulator 240 to produce g(t) according to equation (5). In this case, the interpolator 200 must perform n+1 multiplications and n+1 accumulations.
FIG. 4 shows another conventional interpolator 300 for interpolating audio sample data. As before, the interpolator 300 has an n.times.b bit RAM 310 and an (L.times.n).times.b bit ROM 320. Unlike before, each tap coefficient P.sub.1 (i) stored in the ROM 320 is chosen to be a power of two with only two or three non-zero bits. In operation, each of the n samples is sequentially outputted from the RAM 310 to a shift register 330. The corresponding n tap coefficients are sequentially outputted to a control circuit 340. The control circuit multiplies each tap coefficient with its corresponding sample according to Booth's algorithm. That is, for each non-zero bit q where 0.ltoreq.q.ltoreq.d-1, the sample is shifted q bits to the left and outputted to an accumulator 350 which accumulates each outputted, shifted result. The accumulator 350 accumulates the n products to produce g(t) for a particular t.
FIG. 5 shows yet another conventional interpolator 400 which is disclosed in U.S. Pat. No. 4,862,402. The interpolator 400 interpolates video sample data The sample data ##EQU8## can be written in binary notation as: ##EQU9## where x.sub.m is a vector of bits `` or `1` representing an inputted sample. By combining equations (4) and (6), g(t) may be written as: ##EQU10## Equation (7) is useful for implementing a Booth's algorithm technique for producing the product of each sample and its corresponding tap coefficient (by selectively shifting each sample and accumulating the shifted sample depending on each q.sup.th bit of the tap coefficient). However, the interpolator 400 employs a modified Booth's algorithm technique. In the modified Booth technique, pairs of adjacent q.sub.1.sup.th, q.sub.2.sup.th bits 0.ltoreq.q.sub.1 .ltoreq.d, q.sub.2 =q.sub.1 +1 of the tap coefficient are simultaneously used to selectively accumulate the sample shifted q.sub.1 and q.sub.2 =q.sub.1 +1 bits to the left. Two bit planes of the input signal X can be merged by separating the summation from m=0 to b-1 into parallel even and odd summations. Equation (7) may then be rewritten as: ##EQU11##
In the interpolator 400, a module 410 is provided for preprocessing the tap coefficients P.sub.s (i) and for outputting the processed results to modules 420-0, 420-1, . . . , 420-R where R=b/2-1. Each tap coefficient P.sub.s (i) is sequentially loaded into the module 410 via the line 411. The n tap coefficients P.sub.s (i) are shifted into a first shift register column 412. Furthermore, a multiplier 414 and adder 416 compute 3.multidot.P.sub.s (i) for each coefficient and sequentially shift the n values 3.multidot.P.sub.s (i) into the shift register column 418. Once fully loaded, the module 410 outputs, in parallel, pairs of coefficients P.sub.s (i), 3.multidot.P.sub.s (i) for each i from 0 to n-1 and a particular value of s. Furthermore, each shift register column 412 and 418 is provided with L.multidot.n registers (e.g., 412-0-1, . . . , 412-0-L) for storing coefficients P.sub.s (i), 3.multidot.P.sub.s (i), respectively, for each s and a multiplexer (e.g., 413-1, and 415-1) for outputting appropriate coefficient pairs depending on the inputted sample ##EQU12##
Each of the modules 420-0, 420-1, . . . , 420-R receives a corresponding adjacent pair of bits X.sub.2r, X.sub.2r+1 of an inputted sample ##EQU13## (the module 420-0 receives the bits X.sub.0, X.sub.1, the module 420-1 receives the bits X.sub.2, X.sub.3, etc.). Within each module, e.g., the module 420-0, the inputted pair of bits X.sub.0, X.sub.1 are decoded in a decoder 421. The decoded bits are then inputted as selector control signals to n multiplexers 422-0, 422-1, . . . , 422-(n-1). Each i.sup.th multiplexer (where 0.ltoreq.i.ltoreq.(n-1)) 422-i receives a corresponding pair of coefficients P.sub.s (i), 3.multidot.P.sub.s (i) and selects one of the values 0, P.sub.s (i), 2.multidot.P.sub.s (i), 3.multidot.P.sub.s (i) (depending on the decoded sample bits) to produce the partial product: ##EQU14## The n partial products are outputted from the multiplexers 422-0 to 422-(n-1) to a summation stage 424 which adds up the partial products to produce the sum: ##EQU15## Each of the sums f.sub.0 (t), f.sub.1 (t), . . . , f.sub.R (t) outputted from the multiplier modules 420-0, 420-1, . . . , 420-R are added together by a plurality of adders interconnected in a binary adder tree 430 to produce g(t).
Each of the prior art interpolators has disadvantages. The interpolator 200 is disadvantageous because many time consuming multiplications (and many additions, which are time consuming to a lesser degree) are required to produce each g(t). The interpolator 300 is disadvantageous because each tap coefficient must be a power of two. This can compromise the performance of the interpolator 300. In particular, it is very difficult to meet certain desired frequency responses in certain applications using the interpolator 300. The interpolator 400 is fast but occupies a very large surface area on an IC chip.
It is therefore the object of the present invention to provide a polyphase FIR filter which overcomes the disadvantages of the prior art.